package com.yanceysong.codetop.s31_s40;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class S34_Mid_93_复原IP地址 {
    // 结果集：收集所有符合条件的IP地址
    private final List<String> results = new ArrayList<>();
    // 当前构造路径：存放已经选择的每一段
    private final List<String> segments = new ArrayList<>();

    /**
     * S34_Mid_93_复原IP地址 (Restore IP Addresses)
     * LeetCode: <a href="https://leetcode.cn/problems/restore-ip-addresses/">...</a>
     * ------------------------------------------------------------------
     * 题目：
     * 给定一个只包含数字的字符串 s，表示一串连续的数字。
     * 请在其中插入 3 个点 '.' 将其分割成 4 段，使得每一段都构成一个 合法的 IPv4 地址段，返回所有可能的结果。
     * 规则：
     * 1. IPv4 一共 4 段，每段是 0~255 的十进制整数。
     * 2. 除了单独的 "0" 之外，不能有前导 0，例如："01"、"00" 非法。
     * 3. 不允许重新排序或丢弃任何字符，必须按原顺序切分。
     * 4. 结果可以按任意顺序返回。
     * ------------------------------------------------------------------
     * 示例：
     * 输入: s = "25525511135"
     * 输出: ["255.255.11.135", "255.255.111.35"]
     * 解释: 合法的拆分方式有两个，其它方式违规于区间或前导0。
     * <p>
     * 输入: s = "0000"  → 输出: ["0.0.0.0"]
     * 输入: s = "101023" → 输出: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
     * ------------------------------------------------------------------
     * 解题思路（回溯 + 剪枝）：
     * 我们需要依次选择 4 段，每段长度可以是 1~3 个字符，并且满足合法性：
     * . - 数值范围: 0 <= value <= 255
     * . - 不能有前导 0：如果首字符为 '0'，该段长度只能是 1
     * . - 剩余字符数量必须可行： (剩余字符数) 必须在 [剩余段数, 剩余段数*3] 之间，否则直接剪枝
     * <p>
     * 递归框架：
     * dfs(原字符串, 当前下标 index, 剩余还需要的段数 segmentsRemaining)
     * 结束条件：segmentsRemaining == 0 且 index == s.length() → 收集答案
     * <p>
     * ASCII 回溯树（示例："25525511135"，仅展示第一层部分扩展）：
     * . index=0 选择长度1..3
     * (level0) []
     * ├── "2"
     * │    ├── "5"
     * │    │    ├── "5" ...
     * │    │    └── "55" ...
     * │    └── "55"
     * │         ├── "2" ...
     * │         └── "25" ...
     * ├── "25"
     * │    ├── "5" ...
     * │    └── "52"(继续, 但后面可能因值/长度剪枝)
     * └── "255"
     * ├── "2"
     * │    ├── "5" ...
     * │    └── "55" ...
     * ├── "25"
     * │    ├── "5" ...
     * └── "255"
     * ├── "11"
     * │    ├── "1" -> "135" ✅
     * │    └── "13" -> "5"  ✅
     * └── "111"
     * └── "35" ✅
     * <p>
     * 剪枝案例：如果后面剩余字符过多/过少，不再进入递归。
     * <p>
     * 关键洞察 / 常见错误：
     * 1. 前导 0：段以 '0' 开头时，不能继续扩展更长的段。
     * 2. 段值大于 255：>=256 直接停止该长度尝试（更长只会更大，提前 break 更高效）。
     * 3. 长度剪枝：若剩余字符数 不在 [segmentsRemaining, segmentsRemaining*3] 范围内，提前返回。
     * 4. 复用临时列表存放当前路径，回溯时弹出最后一段。
     * <p>
     * 时间复杂度：最多 O(3^4) = O(81) 个分支（常数级），对每个分支切片/解析数字 O(1~3)。总体非常小。
     * 空间复杂度：递归深度 <= 4，路径存储常数级，结果依赖输出数量。
     * ------------------------------------------------------------------
     * 可扩展思考：
     * 若题目改为 IPv6（8段十六进制，允许前导0），思路仍可复用，只需调整合法性判断与段长度范围。
     */
    public List<String> restoreIpAddresses(String s) {
        results.clear();
        segments.clear();
        // 长度剪枝：最短 4 (1*4)，最长 12 (3*4)
        if (s == null || s.length() < 4 || s.length() > 12) {
            return Collections.emptyList();
        }
        backtrack(s, 0, 4);
        return results;
    }

    /**
     * 回溯函数
     *
     * @param s                 原始字符串
     * @param index             当前处理到的下标位置（下一段起始）
     * @param segmentsRemaining 还需要补齐的段数（初始为 4）
     */
    private void backtrack(String s, int index, int segmentsRemaining) {
        // 如果剩余段数为0，则必须同时恰好用完所有字符
        if (segmentsRemaining == 0) {
            if (index == s.length()) {
                results.add(String.join(".", segments));
            }
            return; // 无论是否成功收集，都要结束这一条路径
        }

        int charsLeft = s.length() - index; // 剩余未使用字符数
        // 关键剪枝：剩余字符数必须落在可形成的最小与最大范围内
        if (charsLeft < segmentsRemaining || charsLeft > segmentsRemaining * 3) {
            return; // 不可行，直接剪枝
        }

        // 尝试当前段的长度：1 ~ 3
        for (int strEndIndex = index; strEndIndex < s.length() && strEndIndex < index + 3; strEndIndex++) {
            // 前导0处理：如果首位是 '0'，该段只能是单个 '0'
            // 首位是0，如果后面还有数字式不对的
            if (s.charAt(index) == '0' && strEndIndex > index) {
                break; // 直接break（不是return），避免"0X"继续扩展
            }
            // 解析当前段字符串
            String segment = s.substring(index, strEndIndex + 1);
            int value = Integer.parseInt(segment);
            if (value > 255) {
                break; // 超过255后更长只会更大，直接剪枝这一层后续长度
            }
            // 做选择
            segments.add(segment);
            backtrack(s, strEndIndex + 1, segmentsRemaining - 1);
            // 撤销选择
            segments.remove(segments.size() - 1);
        }
    }

    // ---------------------------------- 测试主程序 ----------------------------------
    public static void main(String[] args) {
        S34_Mid_93_复原IP地址 solver = new S34_Mid_93_复原IP地址();
        System.out.println("=== 复原IP地址 测试开始 ===\n");

        testExample1(solver);          // 题目示例1
        testExample2(solver);          // 题目示例2
        testExample3(solver);          // 题目示例3
        testAllZeros(solver);          // 全 0 情况
        testLeadingZeroTrap(solver);   // 前导0陷阱
        testBoundary255(solver);       // 边界 255 测试
        testInvalidLengthShort(solver);// 长度过短
        testInvalidLengthLong(solver); // 长度过长
        testPermutationStyle(solver);  // 常见混合
        testSingleResult(solver);      // 唯一结果
        testNoResult(solver);          // 无任何结果

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void printResult(String input, List<String> res, String expectHint) {
        System.out.println("输入: " + input);
        System.out.println("输出: " + res);
        if (expectHint != null) {
            System.out.println("备注/期望提示: " + expectHint);
        }
        System.out.println("结果数量: " + res.size());
        System.out.println("---");
    }

    // 测试1：题目示例1
    private static void testExample1(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试1] 示例: 25525511135");
        List<String> res = solver.restoreIpAddresses("25525511135");
        printResult("25525511135", res, "应包含: 255.255.11.135, 255.255.111.35");
        assert res.contains("255.255.11.135") && res.contains("255.255.111.35");
    }

    // 测试2：题目示例2
    private static void testExample2(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试2] 示例: 0000");
        List<String> res = solver.restoreIpAddresses("0000");
        printResult("0000", res, "唯一: 0.0.0.0");
        assert res.size() == 1 && "0.0.0.0".equals(res.get(0));
    }

    // 测试3：题目示例3
    private static void testExample3(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试3] 示例: 101023");
        List<String> res = solver.restoreIpAddresses("101023");
        printResult("101023", res, "多种组合, 检查包含 1.0.10.23 等");
        assert res.contains("1.0.10.23");
    }

    // 测试4：全0
    private static void testAllZeros(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试4] 全0: 00000000");
        List<String> res = solver.restoreIpAddresses("00000000");
        printResult("00000000", res, "大量 0.* 组合, 实际应为 0.0.0.0.0.0? 不行, 只能4段 -> 0.0.0.000? 也不行(前导0) -> 合法拆分有限");
        // 合法拆分：0.0.0.000 (非法) 所以真实只可能: 0.0.0.0 以及其它? 实际长度8 => 分成 2/2/2/2 或 1/1/3/3等, 但前导0限制 => 只能全部单个0 => 0.0.0.000(非法),
        // 所以没有方案? 反例: 00000000 长度8 > 4*1=4 < 4*3=12, 可以拆: 0.0.0.000(非法) 0.0.00.000(非法) ... 最终只剩 0.0.0.0 与剩余字符不匹配 -> 实际无结果
        // 验证：
        assert res.isEmpty();
    }

    // 测试5：前导0陷阱
    private static void testLeadingZeroTrap(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试5] 前导0陷阱: 010010");
        List<String> res = solver.restoreIpAddresses("010010");
        printResult("010010", res, "经典案例, 常见答案包含: 0.10.0.10, 0.100.1.0");
        assert res.contains("0.10.0.10") && res.contains("0.100.1.0");
    }

    // 测试6：边界255
    private static void testBoundary255(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试6] 边界255: 255255255255");
        List<String> res = solver.restoreIpAddresses("255255255255");
        printResult("255255255255", res, "唯一: 255.255.255.255");
        assert res.size() == 1 && res.get(0).equals("255.255.255.255");
    }

    // 测试7：长度过短
    private static void testInvalidLengthShort(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试7] 长度过短: 123");
        List<String> res = solver.restoreIpAddresses("123");
        printResult("123", res, "不足以分成4段");
        assert res.isEmpty();
    }

    // 测试8：长度过长
    private static void testInvalidLengthLong(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试8] 长度过长: 1234567890123");
        List<String> res = solver.restoreIpAddresses("1234567890123");
        printResult("1234567890123", res, "超过 12 位 不可能");
        assert res.isEmpty();
    }

    // 测试9：混合常见
    private static void testPermutationStyle(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试9] 常见混合: 172162541");
        List<String> res = solver.restoreIpAddresses("172162541");
        printResult("172162541", res, "检查部分合法性");
        // 简单断言：至少有结果
        assert !res.isEmpty();
    }

    // 测试10：唯一结果
    private static void testSingleResult(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试10] 唯一结果: 1111");
        List<String> res = solver.restoreIpAddresses("1111");
        printResult("1111", res, "应该唯一: 1.1.1.1");
        assert res.size() == 1 && res.get(0).equals("1.1.1.1");
    }

    // 测试11：无结果案例
    private static void testNoResult(S34_Mid_93_复原IP地址 solver) {
        System.out.println("[测试11] 无结果: 256256256256");
        List<String> res = solver.restoreIpAddresses("256256256256");
        printResult("256256256256", res, "所有段都 >255");
        assert res.isEmpty();
    }
}
